package com.bascker.algorithm.practice.stack.decode_string;

import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

public class Solution {

    // 左括号
    private final char left = '[';

    // 指针：用于遍历 s
    private int p = 0;

    public String decodeString(String s) {
        // 声明一个栈，存储数字、字母、"[" 括号，遇到右括号“]”时出栈
        final LinkedList<String> stack = new LinkedList<>();

        while (p < s.length()) {
            char ch = s.charAt(p);

            // 遇到数字, 数字入栈
            if (Character.isDigit(ch)) {
                // 此处不用手动 p ++ 了，因为 getNumber 中做了移位操作
                stack.addLast(getNumber(s));
            }
            // 遇到字母 or 左括号
            else if (Character.isLetter(ch) || ch == left) {
                stack.addLast(String.valueOf(ch));
                p ++;
            }
            // 遇到右括号
            else {
                // 出栈：直到遇到左括号
                final LinkedList<String> sub = new LinkedList<>();
                while (!String.valueOf(left).equals(stack.peekLast())) {
                    sub.addLast(stack.pollLast());
                }
                // 翻转数据: 因为栈先进后出的特性，需要反转一下变成正常的顺序
                Collections.reverse(sub);

                // 获取字符串
                String subStr = getString(sub);

                // 左括号出栈
                stack.pollLast();

                // 得到数字
                int repeat = Integer.parseInt(stack.pollLast());

                // 解码: 子串重复 x 次
                StringBuilder sb = new StringBuilder();
                while (repeat > 0) {
                    sb.append(subStr);
                    repeat --;
                }
                String decode = sb.toString();

                // 重点：将构造好的数据入栈 -> 可能存在嵌套括号
                stack.addLast(decode);

                // 指针移动
                p ++;
            }
        }

        // 从头到尾组装最终解码数据
        return getString(stack);
    }

    // 顺序遍历list组装字符串
    private String getString(List<String> list) {
        StringBuilder sb = new StringBuilder();
        for (String v : list) {
            sb.append(v);
        }

        return sb.toString();
    }

    private String getNumber(String s) {
        final StringBuilder sb = new StringBuilder();
        // 因为可能是多位数字, 如10
        while (Character.isDigit(s.charAt(p))) {
            sb.append(s.charAt(p));
            p ++;
        }

        return sb.toString();
    }

}
